package leetcode101_xqzhao

// TODO 二叉树展开为链表 【-】 递归 | 队列
// TODO 也有纯递归地实现方式, 但比较难想

func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	if root.Left == nil && root.Right == nil {
		return
	}
	queue := make([]*TreeNode, 0)

	var dfs114 func(node *TreeNode)
	dfs114 = func(node *TreeNode) {
		// 递归结束条件
		if node == nil {
			return
		}

		// 保存结果 + 继续递归: 先序遍历
		queue = append(queue, node)
		dfs114(node.Left)
		dfs114(node.Right)
	}

	dfs114(root)

	for i := 0; i < len(queue); i++ {
		root.Left = nil
		root.Right = queue[i]
		root = root.Right
	}
}
